//
// Created by vista on 2017/12/15.
//

#ifndef P_P16_H
#define P_P16_H

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
using namespace std;

class Solution {
public:
    // l - include , r - exclude , t - target
    vector<int>::iterator binary_search_nearly(vector<int>::iterator l,vector<int>::iterator r,int t){
        auto itr = l + (r-l)/2;
        if(r - l == 1) {
            return l;
        }else if(*itr > t){
            return binary_search_nearly(l,itr,t);
        }else
            return binary_search_nearly(itr,r,t);
    }

    void cmp(int &nearlySum , int &minDistance,int left,int right,vector<int>::iterator ptr,int t){
        int result = left + right + *ptr;

        if( abs(t-result) < minDistance ){
            minDistance = abs(t-result);
            nearlySum = result;
        }
    }

    int threeSumClosest(vector<int>& nums, int target) {
        int nearlySum  = 0;
        int minDistance = INT32_MAX;

        if(nums.size() < 3)
            0;

        sort(nums.begin(),nums.end());

        int l = 0, r = static_cast<int>(nums.size() - 1);

        while ( r-l >= 2) {
            int left = nums[l];
            do {
                int right = nums[r];
                int mid = target - left - right;
//                if(mid > right){
//                    break;
//                }
                auto ptr = binary_search_nearly(nums.begin() + l + 1, nums.begin() + r, mid);

                cmp(nearlySum,minDistance,left,right,ptr,target);

                if(ptr - nums.begin() != l+1){
                    cmp(nearlySum,minDistance,left,right,ptr-1,target);
                }

                if(ptr - nums.begin() != r-1){
                    cmp(nearlySum,minDistance,left,right,ptr+1,target);
                }

                do{
                    --r;
                }while (nums[r] == right);

            } while (r - l >= 2);
            do{
                ++l;
            }while (nums[l] == left);
            r = static_cast<int>(nums.size() - 1);
        }

        return nearlySum;
    }
};

#endif //P_P16_H
